"""
时间复杂度：O(nlogn)
"""
import random
import sys

from SortingAlgorithm.cal_time.cal_time import cal_time

# sys.setrecursionlimit(10000)


# 快速排序
@cal_time(name="快速排序时间")
def quick_sort(arr, key=lambda a: a):
    _quick_sort(arr, key=key)


def _quick_sort(arr, _l=None, _r=None, key=lambda a: a, reverse=False):
    '''
    :param arr: 要排序的列表
    :param _l:  最左边指针
    :param _r:  最右边指针
    :return:
    '''
    if _l is None and _r is None:
        _l, _r = 0, len(arr)-1

    l, r, t = _l, _r, 0
    if r - l > 0:
        # index = random.randint(1, r)
        index = l + (r-l) // 2  # 不取第一个元素为比较值, 而是取中间元素来当比较值，为的就是避免最坏的情况出现，导致变成O(n**2), 同时也很有可能超出递归深度
        arr[_l], arr[index] = arr[index], arr[_l]
        t = arr[_l]
        while l < r:
            while l < r and key(arr[r]) >= key(t):
                r = r - 1
            arr[l] = arr[r]
            while l < r and key(arr[l]) <= key(t):
                l = l + 1
            arr[r] = arr[l]
        arr[r] = t
        _quick_sort(arr, _l, l-1, key=key)
        _quick_sort(arr, l+1, _r, key=key)


if __name__ == '__main__':
    # li = [23,1,6,77,8,-11,100,11.1,99,99.0, 24,21,4, 101, 56, 66]
    li = list(range(10000))
    random.shuffle(li)

    quick_sort(li)
    # print(li)
